#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "huffman.h"
#include "tipoAudio.h"
#include "gerenciadorArquivo.h"
/*Funcoes de manipulacao da estrutura (lista e arvore)
 * busca o elemento imediatamente anterior a *elem
 * ignora pais e end of file*/
HuffmanList *busca( HuffmanList *lista, HuffmanList *elem){
	if(elem->end_of == 1 || elem->dad == 1)
		return NULL;
	if(lista->nextItem == NULL)
		return NULL;
	if( (lista->nextItem)->value == elem->value)
		return lista;
	return busca(lista->nextItem,elem);
}
/*Busca elemento ultimo elemento com frequencia menor que o segundo parametro*/
HuffmanList *busca_imed_menor( HuffmanList *lista, unsigned short int frequencia){
	if( lista->nextItem == NULL || (lista->nextItem)->frequency > frequencia)
		return lista;
	return busca_imed_menor(lista->nextItem,frequencia);
}
/*Remove o elemento apontado por *elem_anterior na lista*/
void remover(HuffmanList **elem_anterior){
	HuffmanList *aux;
	aux = (*elem_anterior)->nextItem;
	(*elem_anterior)->nextItem = aux->nextItem;
}
/*Remove o primeiro elemento da lista*/
void remover_primeiro (HuffmanList **lista){
	HuffmanList *aux;
	aux = *lista;
	(*lista) = aux->nextItem;
}
/*Insere um elemento na lista*/
void inserir(HuffmanList **lista, HuffmanList *elem){
	HuffmanList *aux, *aux2;
//casp a lista ainda esteja nula
	if(*lista == NULL)
		*lista = elem;
	else {//senao
		//ve se um elemento igual esta na lista, se sim, adiciona a frequencia do elemento da lista
		//ao elemento a ser adicionado, e o remove da lista
		if (((*lista)->value == elem->value) && elem->dad == 0 && elem->end_of  == 0){
			elem->frequency=(*lista)->frequency+1;
			elem->oneChild=(*lista)->oneChild;
			elem->zeroChild=(*lista)->zeroChild;
			elem->end_of=(*lista)->end_of;
			elem->dad=(*lista)->dad;
			remover_primeiro(lista);
		}
		else {
			aux = busca(*lista, elem);
			if (aux != NULL){
				elem->frequency=(aux->nextItem)->frequency+1;
				elem->oneChild=(aux->nextItem)->oneChild;
				elem->zeroChild=(aux->nextItem)->zeroChild;
				elem->end_of=(aux->nextItem)->end_of;
				elem->dad=(aux->nextItem)->dad;
				remover(&aux);
			}
		}
		//Caso o primeiro da lista tenha sido removido acima
		if(*lista == NULL)
			(*lista)=elem;
		//Caso o primeiro tenha frequencia maior que o elemento a ser
		//adicionado, adiciona o elemento no inicio da lista
		if ((*lista)->frequency > elem->frequency){
			aux = *lista;
			*lista = elem;
			elem->nextItem=aux;
		}
		else {
			//Caso contrario busca onde o elemento deve ser adicionado e o adiciona
			aux = busca_imed_menor(*lista, elem->frequency);
			if (aux != NULL){
				if(aux->nextItem == NULL){
					aux->nextItem = elem;
				}
				else {
					aux2=aux->nextItem;
					aux->nextItem=elem;
					elem->nextItem=aux2;
				}
			}
		}
	}
}
//Funcao para criar um elemento generico
HuffmanList *criar_elem(unsigned short int valor){
	HuffmanList* elem;
	elem = (HuffmanList *) malloc(sizeof(HuffmanList));

	elem->frequency=1;
	elem->nextItem=NULL;
	elem->value=valor;
	elem->oneChild=NULL;
	elem->zeroChild=NULL;
	elem->end_of = 0;
	elem->dad = 0;

	return elem;
}
//Cria a arvore a partir da lista
void criar_arvore_huffmann(HuffmanList **lista){
	HuffmanList *pai;
	pai = NULL;
	if((*lista)->nextItem != NULL){
		pai = criar_elem(0);
		pai->frequency = (*lista)->frequency + ((*lista)->nextItem)->frequency;
		pai->zeroChild=*lista;
		pai->oneChild=(*lista)->nextItem;
		pai->dad = 1;

		(*lista)=(*lista)->nextItem->nextItem;
		inserir(lista, pai);

		criar_arvore_huffmann(lista);
	}
}
//Funcao auxiliar para encontrar o maior
short int maior(short int a, short int b){
    if(a > b)
        return a;
    else
        return b;
}
//Encontra a profundidade da arvore
short int profundidade(HuffmanList *arvore){
	if((arvore == NULL) || (arvore->zeroChild == NULL && arvore->oneChild == NULL))
	       return 0;
	   else
	       return 1 + maior(profundidade(arvore->zeroChild), profundidade(arvore->oneChild));

}
//Conta o numero de folhas da arvore
int contarFolhas(HuffmanList *arvore){
   if(arvore == NULL)
        return 0;
   if(arvore->zeroChild == NULL && arvore->oneChild == NULL)
        return 1;
   return contarFolhas(arvore->zeroChild) + contarFolhas(arvore->oneChild);
}
//Busca o elemento de final de arquivo na arvore
void buscar_eof(HuffmanList *arvore, char *codigoHuffman, char *encontrou){
	if(*encontrou == 0 && arvore->end_of==0){
		if(arvore->zeroChild != NULL){
			strcat(codigoHuffman, "0");
			buscar_eof(arvore->zeroChild,codigoHuffman, encontrou);
		}
		if(arvore->oneChild != NULL){
			strcat(codigoHuffman, "1");
			buscar_eof(arvore->oneChild,codigoHuffman, encontrou);
		}
		if(*encontrou == 0)
		codigoHuffman[strlen(codigoHuffman)-1]='\0';
	}
	else
		*encontrou=1;
}
//Cria a tabela a ser enviada a partir da arvore
void criar_tabela(HuffmanList *arvore, HuffmanTable *tabela, int *i, int nelem, char *acabou){
	if(arvore->zeroChild != NULL){
		strcat(tabela[*i].code, "0");
		criar_tabela(arvore->zeroChild, tabela, i, nelem, acabou);
	}
	if(arvore->oneChild != NULL){
		strcat(tabela[*i].code, "1");
		criar_tabela(arvore->oneChild, tabela, i, nelem, acabou);
	}
	else{
		tabela[*i].value = arvore->value;
		if(*i < nelem-1){
			strcpy(tabela[(*i)+1].code, tabela[*i].code);
			(*i)++;
		}
	}
	if(*acabou==0)
	{
		tabela[*i].code[strlen(tabela[*i].code)-1]='\0';
		if(*i >= nelem-1)
			*acabou = 1;
	}

}
//Ordena a tabela pelo tamanho do codigo de Huffmann
void ordenar_tabela(HuffmanTable *tabela, int nelem){
	int i, j;
	HuffmanTable aux;
	aux.code = (char*) malloc(sizeof(char)*32);

	for(i=nelem-1; i>=1; i--){
		for(j=0; j<i; j++){
			if(strlen(tabela[j].code) > strlen(tabela[j+1].code)){
				strcpy(aux.code, tabela[j].code);
				aux.value=tabela[j].value;

				strcpy(tabela[j].code, tabela[j+1].code);
				tabela[j].value=tabela[j+1].value;

				strcpy(tabela[j+1].code, aux.code);
				tabela[j+1].value=aux.value;
			}
		}
	}
}
//Funcao que faz a compressao de Huffmann
void comprimir_huffman(char *input, char *output ){
	FILE *finput, *foutput;
	int tam_arquivo;
	int num_amostras, prof;
	int i, nelem, dataTogetherSize;
	HuffmanList **lista, *eof;
	unsigned short *amostras_entrada;
	unsigned char *vetor_saida;
	wav_header cabecalho;
	HuffmanHeader cabecalhoHuffman;
	HuffmanTable *tabela;
	char encontrou_eof = 0, criou_tabela=0;
	finput = fopen(input, "rb");
//	foutput = fopen(output, "ab");
	//Le o arquivo descomprimido e encontra seu tamanho
	fread(&cabecalho,sizeof(wav_header),1,finput);
	tam_arquivo = ftell(finput);
	fseek(finput, 0, SEEK_END);
	tam_arquivo = 8*(ftell(finput) - tam_arquivo);
	fseek(finput, sizeof(wav_header), SEEK_SET);

//	fseek(foutput, 0, SEEK_END);
	//
	num_amostras = tam_arquivo/16;
	amostras_entrada = (unsigned short int *) malloc(sizeof(unsigned short int) * num_amostras);
	fread(amostras_entrada, sizeof(unsigned short int), num_amostras, finput);
	fclose (finput);
	lista = (HuffmanList **)malloc(sizeof(HuffmanList*));
	*lista = NULL;
	//Insere os elementos na lista
	for(i=0; i<num_amostras; i++){
		inserir(lista, criar_elem(amostras_entrada[i]));
	}

	eof = criar_elem(0);
	eof->end_of=1;
	//Insere o EOF
	inserir(lista,eof);

	criar_arvore_huffmann(lista);

	nelem=contarFolhas(*lista);
	prof = profundidade(*lista);
	tabela = (HuffmanTable*) malloc(sizeof(HuffmanTable)*nelem);
	for(i=0; i< nelem; i++){
		tabela[i].code = (char*) malloc(sizeof(char)*(prof+1));
		tabela[i].code[0] = '\0';
	}
	i=0;
	criar_tabela(*lista, tabela, &i, nelem, &criou_tabela);
	ordenar_tabela(tabela, nelem);

	vetor_saida = PuttingBitsTogetherTable(TableToBit(prof, nelem,tabela), prof, nelem, &dataTogetherSize);
	cabecalhoHuffman.deep = prof;
	cabecalhoHuffman.nchannels=(char)cabecalho.numChannels;
	cabecalhoHuffman.nelem = nelem;
	cabecalhoHuffman.eof[0]='\0';
	buscar_eof(*lista,cabecalhoHuffman.eof,&encontrou_eof);
	//Escrever o arquivo
	escrever_huffmann(cabecalhoHuffman,vetor_saida,dataTogetherSize,output);
}
/* Transform Table Data in Bit Array */
unsigned short int* TableToBit(short int deep, int NoE, HuffmanTable *table){
	int div, rest;
	unsigned short int *dataBits;
	int i, j, length;

	/* Allocating Memory */
	dataBits = (unsigned short int*)malloc((NoE*(16 + deep + deep))*sizeof(unsigned short int));

	for(i=0; i<NoE; i++){
		div = ((int)table[i].value)/2;
		rest = ((int)table[i].value)%2;

		/* Getting Table Values */
		for(j=15; j>=0; j--){
			dataBits[(16+deep+deep)*i+j] = rest;
			rest = div%2;
			div = div/2;
		}

		/* Getting Code Length */
		length = strlen(table[i].code);
		for(j=16; j<16+deep; j++){
			if(j<16+length){
				dataBits[(16+deep+deep)*i+j] = 1;
			}
			else{
				dataBits[(16+deep+deep)*i+j] = 0;
			}
		}

		/* Getting Table Code */
		for(j=16+deep; j <16+deep+deep; j++){
			if(j<16+deep+length){
				dataBits[(16+deep+deep)*i+j] = (unsigned short int)(table[i].code[j-16-deep] - '0');
			}
			else{
				dataBits[(16+deep+deep)*i+j] = 0;
			}
		}
	}
	return dataBits;
}

/* Transform Table Bit Array in Unsigned Short Int Array*/
unsigned char* PuttingBitsTogetherTable(unsigned short int* dataBits, short int deep, int NoE, int *dataTogetherSize){
	unsigned char *dataTogether;
	int rest;
	int i, j;

	/* Calculating Compressed Data Size */
	(*dataTogetherSize) = (NoE*(16 + deep + deep)/8);
	rest = (NoE*(16 + deep+ deep)%8);
	if (rest == 0){
		dataTogether = (unsigned char*) malloc((*dataTogetherSize)*sizeof(unsigned char));
	}
	else{
		dataTogether = (unsigned char*) malloc(((*dataTogetherSize))*sizeof(unsigned char));
		(*dataTogetherSize)++;
	}

	/* Putting Compressed Bits Together */
	for(i=0; i<(*dataTogetherSize); i++){
			dataTogether[i] = 0; /* Initialize Compressed Value With Zero */
			for(j=0; j<8; j++){
				dataTogether[i] = dataTogether[i] + dataBits[8*i +j]*(pow(2,7-j));
			}
		}
	if(rest == 0){
		return dataTogether;
	}
	else{
		for(j=0; j<rest; j++){
			dataTogether[i] = dataTogether[i] + dataBits[8*i +j]*(pow(2,7-j));
		}
		for(j=rest; j<8; j++){
			dataTogether[i] = dataTogether[i] + 0*(pow(2,7-j));
		}
		return dataTogether;
	}
}

/* Transform Compressed Data Char Array in Bit Array*/
unsigned char* DesassemblingCompData(unsigned char *compData, short int deep, int NoE){
	int div, rest;
	unsigned char *dataBits;
	int i, j;

	/* Allocating Memory */
	dataBits = (unsigned char*)malloc((NoE*(16 + deep + deep))*sizeof(unsigned char));

	for(i=0; i<NoE; i++){
		div = compData[i]/2;
		rest = compData[i]%2;
		for(j=7; j>=0; j--){
			dataBits[(8*i)+j] = rest;
			rest = div%2;
			div = div/2;
		}
	}
	return dataBits;
}

/* Transform Compressed Bit Array in Table Elements*/
void PuttingTableTogetherBits(unsigned char* dataBits, short int deep, int NoE, HuffmanTable* table){
	int i, j, length;

	/* Putting Compressed Bits Together (for table->values) and coping code (for table->code) */
	for(i=0; i<NoE; i++){
		table[i].value = 0 ; /* Initialize Compressed Value With Zero */

		/* Retrieving Value */
		for(j=0; j<16; j++){
			table[i].value = table[i].value + dataBits[(16+deep+deep)*i +j]*(pow(2,15-j));
		}

		/* Retrieving Code Length */
		length = 0;
		for(j=16; j<16+deep; j++){
			length = length + dataBits[(16+deep+deep)*i +j];
		}

		/* Retrieving Code */
		for(j=16+deep; j<16+deep+length; j++){
			table[i].code[j-(16+deep)] = dataBits[(16+deep+deep)*i +j] + '0';
		}
		table[i].code[j-(16+deep)] = '\0';
	}
}

/* Transform File Data in Bit Array */
unsigned short int* FileToBit(short int deep, int NoE, unsigned short int *codeArray){
	int div, rest;
	unsigned short int *dataBits;
	int i, j;

	/* Allocating Memory */
	dataBits = (unsigned short int*)malloc((NoE*(deep))*sizeof(unsigned short int));

	for(i=0; i<NoE; i++){
		div = ((int)(codeArray[i]))/2;
		rest = ((int)(codeArray[i]))%2;
		for(j=15; j>=0; j--){
			dataBits[15*i+j] = rest;
			rest = div%2;
			div = div/2;
		}
	}
	return dataBits;
}

/* Transform File Bit Array (Table->code for each Element) in Unsigned Short Int Array */
unsigned char* PuttingBitsTogetherFile(unsigned short int* dataBits, short int deep, int NoE, int *dataTogetherSize){
	unsigned char *dataTogether;
	int rest;
	int i, j;

	/* Calculating Compressed Data Size */
	*dataTogetherSize = (NoE*(deep)/8);
	rest = (NoE*(16 + deep)%8);
	if (rest == 0){
		dataTogether = (unsigned char*) malloc((*dataTogetherSize)*sizeof(char));
	}
	else{
		dataTogether = (unsigned char*) malloc((++(*dataTogetherSize))*sizeof(char));
	}

	/* Putting Compressed Bits Together */
	for(i=0; i<(*dataTogetherSize); i++){
			dataTogether[i] = 0; /* Initialize Compressed Value With Zero */
			for(j=0; j<8; j++){
				dataTogether[i] = dataTogether[i] + dataBits[8*i +j]*(pow(2,7-j));
			}
		}
	if(rest == 0){
		return dataTogether;
	}
	else{
		for(j=0; j<rest; j++){
			dataTogether[i] = dataTogether[i] + dataBits[8*i +j]*(pow(2,7-j));
		}
		for(j=rest; j<8; j++){
			dataTogether[i] = dataTogether[i] + 0*(pow(2,7-j));
		}

		return dataTogether;
	}
}
//Funcao de descompressao
void descomprimir_huffman(char *output,char *new_output){
	FILE * foutput, *fnew_output;
	HuffmanHeader cabecalhoHuffman;
	HuffmanTable *tabela;
	long int tam_arq;
	unsigned char *bits_em_char;

	int i;


	foutput = fopen(output, "rb");
	//Le o cabecalho de Huffmann criado
	fread(&cabecalhoHuffman.nchannels,sizeof(char),1,foutput);//Numero de canais
	fread(&cabecalhoHuffman.deep, sizeof(char), 1, foutput);//numero maximo de bits da codificacao
	fread(&cabecalhoHuffman.nelem, sizeof(unsigned short int), 1, foutput);//numero de elementos da tabela
	fread(cabecalhoHuffman.eof, sizeof(char), 32, foutput);//Le o codigo do eof

	tabela = (HuffmanTable*) malloc(sizeof(HuffmanTable)* cabecalhoHuffman.nelem);

	for(i=0; i<cabecalhoHuffman.nelem; i++){
		tabela[i].code = (char*) malloc(sizeof(char)*(cabecalhoHuffman.deep+1));
	}
	tam_arq=ftell(foutput);
	fseek(foutput,0,SEEK_END);
	tam_arq=ftell(foutput)-tam_arq;
	fseek(foutput,sizeof(cabecalhoHuffman),SEEK_SET);

	bits_em_char = (unsigned char*) malloc(sizeof(unsigned char)*tam_arq);
	fread(bits_em_char,sizeof(unsigned char),tam_arq,foutput);

	fclose(foutput);

	PuttingTableTogetherBits(DesassemblingCompData(bits_em_char,cabecalhoHuffman.deep,
			cabecalhoHuffman.nelem),cabecalhoHuffman.deep,cabecalhoHuffman.nelem,tabela);

}

void codificacao_huffman(char *input, char *output){
     int op;
     char new_output[30]="Audio/";
     char aux[30];
 //    system("cls");
     printf("\n");
     printf("****************** (Des)Comprimir por Huffman ********************\n\n");

     do{
        printf("\n");
        printf("1 - Comprimir\n");
        printf("2 - Descomprimir\n");
        printf("3 - Voltar\n");
        scanf("%d", &op);
        printf("\n\n");
        
        switch (op)
        {
               case 1: comprimir_huffman(input, output);break;
               case 2:
            	   printf("Digite o nome do novo arquivo de saida\n");
            	   scanf("%s", aux);
            	   strcat(new_output, aux);
            	   descomprimir_huffman(output, new_output);break;
               default: break;
        }
        }while(op != 3);
}
//Escreve o arquivo comprimido
void escrever_huffmann (HuffmanHeader cabecalho, unsigned char *dados, int tam_dados, char *nome_arquivo){
	FILE *saida;
	int i;

	if((saida = fopen(nome_arquivo, "wb")) == NULL)
	{
		printf("Nao foi possivel abrir %s \n", nome_arquivo);
	}

	fwrite(&(cabecalho.nchannels), sizeof(char), 1, saida);
	fwrite(&(cabecalho.deep), sizeof(char), 1, saida);
	fwrite(&(cabecalho.nelem), sizeof(unsigned short int), 1, saida);
	fwrite(cabecalho.eof, sizeof(char), 32, saida);
	for(i=0; i<tam_dados; i++){
		fprintf(saida, "%c", dados[i]);
	}

	fclose(saida);
}
